import time
import random
import numpy as np


def BubbleSort(li):
    n = len(li)
    for i in range(n-1):
        for j in range(n-i-1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
    return li

def QuickSort(li, left, right):
    def partition(li, left, right):
        random_index = random.randrange(left, right)
        li[left], li[random_index] = li[random_index], li[left]
        temp = li[left]
        while left < right:
            while li[right] > temp and left < right:
                right -= 1
            li[left] = li[right]
            while li[left] <= temp and left < right:
                left += 1
            li[right] = li[left]
        li[left] = temp
        return left

    if left < right:
        mid = partition(li, left, right)
        QuickSort(li, left, mid-1)
        QuickSort(li, mid+1, right)

    return li

def HeapSort(li):
    def sift(li, low, high):
        i = low
        j = 2 * i + 1
        temp = li[low]
        while j <= high:
            if j + 1 <= high and li[j + 1] > li[j]:
                j += 1
            if li[j] > temp:
                li[i] = li[j]
                i = j
                j = 2 * i + 1
            else:
                break
        li[i] = temp


    n = len(li)
    for i in range((n - 2) // 2, -1, -1):
        sift(li, i, n - 1)
    while n - 1 > 0:
        li[0], li[n - 1] = li[n - 1], li[0]
        n -= 1
        sift(li, 0, n - 1)
    return li

def RadixSort(li):
    max_num = max(li)
    it = 0
    while 10 ** it <= max_num:
        buckets = [[] for i in range(10)]
        for var in li:
            digt = (var // 10 ** it) % 10
            buckets[digt].append(var)
        li.clear()
        for buc in buckets:
            li.extend(buc)
        it += 1
    return li


def BucketSort(li, n=100, max_num=10000):
    buckets = [[] for i in range(n)]
    for var in li:
        i = min(var//(max_num//n), n-1)
        buckets[i].append(var)
        for j in range(len(buckets[i])-1, 0, -1):
            if buckets[i][j] < buckets[i][j-1]:
                buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j]
    li.clear()
    for i in buckets:
        li.extend(i)
    return li


def ShellSort(li):
    def insert_sort_gap(li, gap):
        for i in range(gap, len(li)):
            temp = li[i]
            j = i - gap
            while j >= 0 and li[j] > temp:
                li[j+gap] = li[j]
                j -= gap
            li[j+gap] = temp
        return li
    d = len(li)//2
    while d >= 1:
        insert_sort_gap(li, gap=d)
        d //= 2
    return li

def MergeSort(li, low, high):
    def merge(li, low, mid, high):
        temp = []
        i = low
        j = mid + 1
        while i <= mid and j <= high:
            if li[i] < li[j]:
                temp.append(li[i])
                i += 1
            else:
                temp.append(li[j])
                j += 1
        while i <= mid:
            temp.append(li[i])
            i += 1
        while j <= high:
            temp.append(li[j])
            j += 1
        li[low:high+1]=temp
    if low < high:
        mid = (low+high)//2
        MergeSort(li, low, mid)
        MergeSort(li, mid + 1, high)
        merge(li,low, mid,high)
    return li

def count_sort(li, max_count):
    count = [0 for i in range(max_count+1)]
    for val in li:
        count[val] += 1
    li.clear()
    for idx, num in enumerate(count):
        for i in range(num):
            li.append(idx)
    return li

# li = list(range(10))
# random.shuffle(li)
# print(li)
#
# li = RadixSort(li)
# print(li)
